package com.xcc.dataStructures.demo04_stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author xiaocheng
 * @date 2020/11/27 9:39
 */
public class PolandNotation {

    public static void main(String[] args) {
        //1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 –
        String experssion = "1+((2+3)*40)-5";
        //首先将expression转换成中缀list集合
        List<String> infixExpressionList = toInfixExpressionList(experssion);
        System.out.println("中缀表达式为:" + infixExpressionList);
        //中缀表达式转后缀表达式
        List<String> sufixExpressionList = toSufixExpressionList(infixExpressionList);
        System.out.println("后缀表达式为:" + sufixExpressionList);
        //计算后缀表达式
        int res = calresult(sufixExpressionList);
        System.out.println("结果为:" + res);
    }

    /**
     * 计算后缀表达式结果
     */
    private static int calresult(List<String> ls) {
        Stack<Integer> nums = new Stack<>();
        for (String s : ls) {
            if (s.matches("\\d+")) {
                nums.push(Integer.parseInt(s));
            } else {
                int num2 = nums.pop();
                int num1 = nums.pop();
                int res = cal(num1, num2, s);
                nums.push(res);
            }
        }
        return nums.pop();
    }

    /**
     * 计算两个数的结果
     */
    private static int cal(int num1, int num2, String s) {
        int res = 0;
        switch (s) {
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num1 - num2;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num1 / num2;
                break;
        }
        return res;
    }

    /**
     * 中缀表达式转后缀表达式
     */
    private static List<String> toSufixExpressionList(List<String> infixExpressionList) {
        java.util.Stack<String> s1 = new java.util.Stack<String>();
        List<String> s2 = new ArrayList<>();
        for (String s : infixExpressionList) {
            if (s.matches("\\d+")) {
                s2.add(s);
            } else if (s.equals("(")) {
                s1.push(s);
            } else if (s.equals(")")) {
                while (true) {
                    String oper = s1.pop();
                    if (oper.equals("(")) {
                        break;
                    } else {
                        s2.add(oper);
                    }
                }
            } else {
                //运算符
                while (true) {
                    //如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
                    if (s1.empty() || "(".equals(s1.peek())) {
                        s1.push(s);
                        break;
                    }
                    int topPri = priority(s1.peek());
                    int curPri = priority(s);
                    //若优先级比栈顶运算符的高，也将运算符压入 s1；
                    if (curPri > topPri) {
                        s1.push(s);
                        break;
                    } else {
                        //若优先级比栈顶运算符的小于等于 将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4-1)与 s1 中新的栈顶运算符相比较
                        String topOper = s1.pop();
                        s2.add(topOper);
                    }
                }
            }
        }

        //将 s1 中剩余的运算符依次弹出并压入 s2
        while (!s1.empty()) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 获取优先级
     */
    private static int priority(String s) {
        if ("/".equals(s) || "*".equals(s)) {
            return 1;
        } else if ("+".equals(s) || "-".equals(s)) {
            return 0;
        } else {
            return -1;
        }
    }

    /**
     * 将字符串转成中缀表达式
     */
    private static List<String> toInfixExpressionList(String experssion) {
        List<String> ls = new ArrayList<>();
        //定义多位数数值
        String nums = "";
        int index = 0;
        String ch = "";
        while (index < experssion.length()) {
            ch = experssion.substring(index, index + 1);
            if (ch.matches("\\d+")) {
                //如果为数值
                nums += ch;
            } else {
                //当当前字符串不为数值类型时  判断nums中是否有值:有值则假如到list中并清空nums
                if (nums != "") {
                    ls.add(nums);
                    nums = "";
                }
                ls.add(ch);
            }
            if ((index == experssion.length() - 1) && nums != "") {
                ls.add(nums);
            }
            index++;
        }
        return ls;
    }

}
